package main

import (
	"fmt"
	"sort"
)

/**
执行用时：0 ms, 在所有 Go 提交中击败了100.00%的用户
内存消耗：3.7 MB, 在所有 Go 提交中击败了95.70%的用户
 */
var ans [][]int
var path []int
var st []bool

func permuteUnique(nums []int) [][]int {

	sort.Slice(nums, func(i, j int) bool {
		return nums[i] < nums[j]
	})

	n := len(nums)
	ans = [][]int{}
	path = make([]int, n)
	st = make([]bool, n)
	dfs(nums, 0)
	return ans
}

func dfs(nums []int, u int) {

	if u == len(nums) {
		t := make([]int, len(path))
		copy(t, path)
		ans = append(ans, t)
		return
	}

	for i := 0; i < len(nums); i++ {
		if !st[i] {
			if i > 0 && nums[i] == nums[i - 1] && !st[i - 1] { continue }
			st[i] = true
			path[u] = nums[i]
			dfs(nums, u + 1)
			st[i] = false
		}
	}
}

func main() {

	nums := []int{1, 2, 3}
	fmt.Println(permuteUnique(nums))
}
